/* 接雨水
    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
    示例 1：
    输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出：6
    解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

    示例 2：
    输入：height = [4,2,0,3,2,5]
    输出：9
*/

#include <iostream>
#include <vector>

using namespace std;

int trap(vector<int> &height)
{
    // 三根柱子开始才能储水
    if (height.size() < 3)
    {
        return 0;
    }

    int left = 0, right = height.size() - 1;
    int leftMax = 0, rightMax = 0;
    int waterCnt = 0;

    // 双指针，左指针小于右指针一直循环
    while (left < right)
    {
        // 如果左边高度小于右边高度就操作左边
        if (height[left] < height[right])
        {
            if (height[left] >= leftMax)
            {
                leftMax = height[left];
            }
            else
            {
                waterCnt += leftMax - height[left];
            }

            left++;
        }
        // 操作右边
        else
        {
            if (height[right] >= rightMax)
            {
                rightMax = height[right];
            }
            else
            {
                waterCnt += rightMax - height[right];
            }

            right--;
        }
    }

    return waterCnt;
}

int main()
{
    vector<int> height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    cout << "Rain:" << trap(height) << endl;

    return 0;
}